package com.sunkq.test;

import java.util.*;

public class Solution {
    public static void main(String[] args) {
        ListNode head = new ListNode();
        ListNode tail = new ListNode();
        tail.val = 2;
        head.val = 1;
        head.next = tail;
        traverse(head);
    }

    /* 递归遍历单链表，倒序打印链表元素 */
    public static void traverse(ListNode head) {
        if (head == null) {
            return;
        }
        traverse(head.next);
        // 后序位置
        System.out.println((head.val));
    }

    public int[] levelOrder(TreeNode root) {
        if (root == null) return new int[0];
        Queue<TreeNode> queue = new LinkedList() {{
            add(root);
        }};
        ArrayList<Integer> ans = new ArrayList<>();
        while (!queue.isEmpty()) {
            TreeNode node = queue.poll();
            ans.add(node.val);
            if (node.left != null) queue.add(node.left);
            if (node.right != null) queue.add(node.right);
        }
        int[] res = new int[ans.size()];
        for (int i = 0; i < ans.size(); i++)
            res[i] = ans.get(i);
        return res;
    }


    public char firstUniqChar(String s) {
        HashMap<Character, Boolean> dic = new HashMap<>();
        char[] sc = s.toCharArray();
        for (char c : sc)
            dic.put(c, !dic.containsKey(c));
        for (char c : sc)
            if (dic.get(c)) return c;
        return ' ';
    }


    private static void testFindNumberIn2DArray() {
        int[][] matrix = {
                {1, 4, 7, 11, 15},
                {2, 5, 8, 12, 19},
                {3, 6, 9, 16, 22},
                {10, 13, 14, 17, 24},
                {18, 21, 23, 26, 30}
        };
        Solution solution = new Solution();
        System.out.println(solution.findNumberIn2DArray(matrix, 8));
    }


    public int minArray(int[] numbers) {
        int i = 0, j = numbers.length - 1;
        while (i < j) {
            int m = (i + j) / 2;
            if (numbers[m] > numbers[j]) i = m + 1;
            else if (numbers[m] < numbers[j]) j = m;
            else j--;
        }
        return numbers[i];
    }

    public boolean findNumberIn2DArray(int[][] matrix, int target) {
        int i = matrix.length - 1, j = 0;
        while (i >= 0 && j < matrix[0].length) {
            if (matrix[i][j] > target) i--;
            else if (matrix[i][j] < target) j++;
            else return true;
        }
        return false;
    }


    private static void testMissingMumber() {
        int[] arr = new int[]{0, 2, 3};
        Solution solution = new Solution();
        System.out.println(solution.missingNumber(arr));
    }


    public int missingNumber(int[] nums) {
        int i = 0, j = nums.length - 1;
        while (i <= j) {
            int m = (i + j) / 2;
            if (nums[m] == m) i = m + 1;
            else j = m - 1;
        }
        return i;
    }

    private static void testSearch() {
        int[] arr = new int[]{5, 7, 7, 8, 8, 10};
        Solution solution = new Solution();
        System.out.println(solution.search(arr, 7));
    }

    public int search(int[] nums, int target) {
        // 搜索右边界 right
        int i = 0, j = nums.length - 1;
        while (i <= j) {
            int m = (i + j) / 2;
            if (nums[m] <= target) i = m + 1;
            else j = m - 1;
        }
        int right = i;
        // 若数组中无 target ，则提前返回
        if (j >= 0 && nums[j] != target) return 0;
        // 搜索左边界 right
        i = 0;
        j = nums.length - 1;
        while (i <= j) {
            int m = (i + j) / 2;
            if (nums[m] < target) i = m + 1;
            else j = m - 1;
        }
        int left = j;
        return right - left - 1;
    }


//    public int search(int[] nums, int target) {
//        HashMap<Integer, Integer>map = new HashMap<>();
//        for (int i = 0; i < nums.length; i++) {
//            if(map.containsKey(nums[i])){
//                map.put(nums[i],map.get(nums[i])+1);
//                continue;
//            }
//            map.put(nums[i],1);
//        }
//        return map.get(target)==null?0:map.get(target);
//    }

    public int findRepeatNumber(int[] nums) {
        Set<Integer> set = new HashSet<>();
        for (int i = 0; i < nums.length; i++) {
            if (set.contains(nums[i])) {
                return nums[i];
            }
            set.add(nums[i]);
        }
        return -1;
    }

    public boolean isStraight(int[] nums) {
        Set<Integer> set = new HashSet();
        int max = 0;
        int min = 14;
        for (int i = 0; i < nums.length; i++) {
            if (0 == nums[i]) {
                return false;
            }
            max = Math.max(max, nums[i]);
            min = Math.min(min, nums[i]);
            if (set.contains(nums[i])) {
                return false;
            }
            set.add(nums[i]);
        }
        return max - min > 5;
    }
}

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int x) {
        val = x;
    }
}

class ListNode {
    int val;
    ListNode next;

    ListNode() {
    }

    ListNode(int val) {
        this.val = val;
    }

    ListNode(int val, ListNode next) {
        this.val = val;
        this.next = next;
    }
}